package week_08;

/**
 * 743. 网络延迟时间
 * 有 n 个网络节点，标记为 1 到 n。
 * <p>
 * 给你一个列表 times，表示信号经过 有向 边的传递时间。
 * times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。
 * <p>
 * 现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
 * 输出：2
 * 示例 2：
 * <p>
 * 输入：times = [[1,2,1]], n = 2, k = 1
 * 输出：1
 * 示例 3：
 * <p>
 * 输入：times = [[1,2,1]], n = 2, k = 2
 * 输出：-1
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/network-delay-time
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class NetworkDelayTime_743 {
    public int networkDelayTime(int[][] times, int n, int k) {
        /**
         * 使用Bellman-ford 算法
         *  dist[y]>dist[x]+z 则用dist[x]+z 更新 dist[y]
         *  对每个边都进行一轮更新
         *  至多更新n-1 轮
         */
        int[] dist = new int[n + 1];
        for (int i = 1; i <= n; i++) dist[i] = (int) 1e9;
        dist[k] = 0;
        for (int iteration = 1; iteration < n; iteration++) {
            boolean update = false;
            for (int i = 0; i < times.length; i++) {
                int[] item = times[i];
                int x = item[0];
                int y = item[1];
                int z = item[2];
                if (dist[y] > dist[x] + z) {
                    dist[y] = dist[x] + z;
                    update = true;
                }
            }
            if (!update) break;
        }

        int ans = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) ans = Math.max(ans, dist[i]);
        return ans == (int) 1e9 ? -1 : ans;
    }
}
